package cn.yuemouren.queue;

/**
 * @Author: Timi
 * @Description: 循环队列
 * @Date: 2020/5/12 8:55
 */
public class LoopQueue<T> implements Queue<T>{

    private final static int DEFAULT_CAPACITY = 20;//默认容量

    private T[] data;
    private int font;//队列首个元素指针
    private int tail;//队列元素最后的后一个位置指针
    private int size;//队列里面元素个数

    public LoopQueue(){
        this(DEFAULT_CAPACITY);
    }

    public LoopQueue(int capacity) {
        this.data = (T[])new Object[capacity+1];
        this.font = 0;
        this.tail = 0;
        this.size = 0;
    }

    @Override
    public void enQueue(T t) {
        if((tail + 1) % data.length == font)
            resize(getCaptity() * 2);
        data[tail] = t;
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public T dnQueue() {
        if(tail == font){
            throw new IllegalArgumentException("Queue is empty");
        }
        T res = data[font];
        data[font] = null;
        font = (font + 1) % data.length;
        size--;
        if(size <= data.length / 2 && getCaptity() / 2 != 0){
            resize(getCaptity() / 2);
        }
        return res;
    }

    @Override
    public T getHead() {
        if(font == tail){
            throw new IllegalArgumentException("Queue is empty");
        }
        return data[font];
    }

    @Override
    public int getSize() {
        return size;
    }

    public int getCaptity() {
        return data.length;
    }

    private void resize(int newCapacity){
        T[] newData = (T[])new Object[newCapacity];
        for(int i = 0; i < size; i++){
            newData[i] = data[(i + font) % data.length];
        }
        data = newData;
        font = 0;
        tail = size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("LoopQueue: [");
        for (int i = font; i != tail; i = (i + 1) % data.length){
            sb.append(data[i]);
            if((i + 1) % data.length != tail){
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }
}
